#include <iostream>
using std::cout;
using std::endl;

// 冒泡排序。缺点：交换三次赋值 耗时
void BubbleSort(int arr[], int size) {
  for (int i = 1; i <= size - 1; ++i) {
    bool hasSwap = false;
    for (int j = 0; j < size - i; ++j) {
      if (arr[j] > arr[j + 1]) {
        int tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
        hasSwap = true;
      }
    }
    if (!hasSwap) return;
  }
}

// 插入排序。常用
void InsertSort(int arr[], int size) {
  for (int i = 1; i <= size - 1; ++i) {
    int value = arr[i];
    int j;
    for (j = i; j > 0; --j) {
      if (value < arr[j - 1]) {
        arr[j] = arr[j - 1];
      } else {
        break;
      }
    }
    arr[j] = value;
  }
}

// 选择排序。缺点：不是稳定排序
void SelectSort(int arr[], int size) {
  for (int i = 1; i <= size - 1; ++i) {
    int minidx = i - 1;
    for (int j = i; j < size; ++j) {
      if (arr[minidx] > arr[j]) {
        minidx = j;
      }
    }
    int tmp = arr[minidx];
    arr[minidx] = arr[i - 1];
    arr[i - 1] = tmp;
  }
}

typedef void (*SortFunc)(int arr[], int size);

void Print(int arr[], int size) {
  for (int i = 0; i < size; ++i) {
    cout << arr[i] << ' ';
  }
  cout << endl;
}

void TestSort(SortFunc sort) {
  // int arr[] = {1};
  // int arr[] = {4, 2, 3, 5, 6, 7};
  int arr[] = {6, 2, 5, 8, 3, 10, 2, 3, 30, 11};
  sort(arr, sizeof(arr) / sizeof(int));
  Print(arr, sizeof(arr) / sizeof(int));
}

int main() {
  TestSort(BubbleSort);
  TestSort(InsertSort);
  TestSort(SelectSort);
}